/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2024-01-04 15:00:57
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-01-27 20:15:54
 * @FilePath: /my_-linux/Pro24/Tree/RBT/RBTree/RBTree.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */

#pragma once//在该头文件当中需要添加#pragma once头文件 否则Map.hpp与Set.hpp的头文件后再次在test.cpp中包含头文件时将会出现枚举重定义等多种问题

#include<iostream>

#include<vector>

enum COLOR{
    RED,
    BLACK
};



template<class T>
struct RBTreeNode{

    RBTreeNode<T> *_left;
    RBTreeNode<T> *_right;
    RBTreeNode<T> *_parent;
    T _data; 
    COLOR _col;

    RBTreeNode(const T& data)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_data(data)
    ,_col(RED)
    {}
};

template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/> // 迭代器的实现
class __RBTree_Iterator
{
    typedef __RBTree_Iterator<T, Ref, Ptr> Self;
    typedef RBTreeNode<T> Node;

public:
    __RBTree_Iterator(Node *node)
        : _node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

    Self& operator++()//前置++
    {
        Node* cur = _node;
        if(cur->_right){
            cur = cur->_right;
            while (cur->_left){
                cur = cur->_left;
            }
            _node = cur;
        }
        else{
            Node *parent = cur->_parent;
            while(parent && cur==parent->_right){
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }

        return *this;
    }

    // Self &operator++()
    // {
    //     if (_node->_right)
    //     {
    //         // 右树的最左节点(最小节点)
    //         Node *subLeft = _node->_right;
    //         while (subLeft->_left)
    //         {
    //             subLeft = subLeft->_left;
    //         }

    //         _node = subLeft;
    //     }
    //     else
    //     {
    //         Node *cur = _node;
    //         Node *parent = cur->_parent;
    //         // 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
    //         while (parent && cur == parent->_right)
    //         {
    //             cur = cur->_parent;
    //             parent = parent->_parent;
    //         }

    //         _node = parent;
    //     }

    //     return *this;
    // }

    Self operator++(int){//后置++
        Node* cur = _node;
        ++*this;
        return Self(cur);
    }

    Self& operator--()
    {

        Node* cur = _node;
        if(cur->_left){
            cur = cur->_left;
            while(cur->_right){
                cur = cur->_right;
            }
            _node = cur;
        }
        else{
            Node *parent = cur->_parent;
            while(parent && cur == parent->_left){
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    // Self &operator--()
    // {
    //     if (_node->_left)
    //     {
    //         Node *subRight = _node->_left;
    //         while (subRight->_right)
    //         {
    //             subRight = subRight->_right;
    //         }

    //         _node = subRight;
    //     }
    //     else
    //     {
    //         // 孩子是父亲的右的那个节点
    //         Node *cur = _node;
    //         Node *parent = cur->_parent;
    //         while (parent && cur == parent->_left)
    //         {
    //             cur = cur->_parent;
    //             parent = parent->_parent;
    //         }

    //         _node = parent;
    //     }

    //     return *this;
    // }

    Self operator--(int)
    {
        Node *cur = _node;
        --*this;
        return Self(cur);
    }

    bool operator!=(const Self &s)
    {
        return _node != s._node;
    }

protected:
private:
    Node *_node;
};

template<class K,class T,class KeyOfT>
class RBTree{

public:
    KeyOfT kot; // KeyOfT
    typedef RBTreeNode<T> Node;
    typedef __RBTree_Iterator<T, T &, T *> iterator;
    typedef __RBTree_Iterator<T, const T &, const T *> const_iterator;

    iterator begin(){
        Node* cur = _root;
        while(cur && cur->_left){
            cur = cur->_left;
        }
        return iterator(cur);
    }


    iterator end(){
        return iterator(nullptr);
    }

    ~RBTree() { 
        _Destory(_root); 
        }

    // 该接口不适合该类型
    // void InOrder(){
    //     _InOrder(_root);
    // }

    Node *Find(const K &key){
        Node* cur = _root;
        while(cur){
            if(key>kot(cur->_data)){
                cur = cur->_right;
            }
            else if (key < kot(cur->_data))
            {
                cur = cur->_left;
            }
            else{
                return cur;
            }
        }
        return nullptr;
    }

    pair<iterator,bool> Insert(const T &data) {
        if(_root == nullptr){
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root),true);
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        while(cur){
            if (kot(cur->_data) < kot(data)) {
                parent = cur;
                cur = cur->_right;
            } 
            else if (kot(cur->_data) > kot(data)) {
                parent = cur;
                cur = cur->_left;
            } 
            else {
              return make_pair(iterator(cur), false);
            }
        }

         Node* newnode = new Node(data);
         cur = newnode;
          if (kot(parent->_data) < kot(data)) {
           parent->_right = cur;
           cur->_parent = parent;
         }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
        
            Node *grandfather = parent->_parent;
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                if(uncle && uncle->_col == RED){
                   
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     
                    if(cur == parent->_left){
                        RotateR(grandfather);

                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);

                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);

                  
                        grandfather->_col = RED;
                        parent->_col = BLACK;

                     }
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return make_pair(iterator(newnode), true);
    }

    bool IsBalance(){
        if(_root == nullptr){
            return true;
        }

        if(_root && _root->_col == RED){
            return false;
        }
        
        std::pair<bool,std::vector<int>> ret ;
        ret.first = true;
        _Check(ret,_root,0);

        if(!ret.first){
            std::cout << "某一路径出现连续红色节点" << std::endl;
        }

        bool to_comp = true;
        size_t _comp = ret.second[0];
        for(auto &it : ret.second){
            if(it != _comp){
                to_comp = false;
                break;
            }

            std::cout << it << std::endl;
        }

        

        return to_comp && ret.first;
    }

    int getHeight()
    {
        return getHeight(_root);
    }

protected:


    void RotateL(Node *parent){


        Node *cur = parent->_right;
        Node *curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node *ppnode = parent->_parent;

        parent->_parent = cur;

        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void RotateR(Node *parent){
        

        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
            curright->_parent = parent;

        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    //  该接口在该处不适合
    // void _InOrder(Node *root){
    //     if(root == nullptr) return ;
    //     _InOrder(root->_left);
    //     std::cout << root->_kv.first << " : " << root->_kv.second << " col : " << root->_col << std::endl;
    //     _InOrder(root->_right);
    // }

    void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
        
        if(root == nullptr){
            ret.first = ret.first && true;
            ret.second.push_back(blackNum);
            
            return;
        }

        if(root->_col == RED && root->_parent->_col == RED){
            ret.first = ret.first && false;
            return ;
        }

        if(root->_col == BLACK){
            blackNum++;
        }

        _Check(ret, root->_left, blackNum);
        _Check(ret, root->_right, blackNum);
    }
    
    int getHeight(Node *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int left = getHeight(root->_left);
        int right = getHeight(root->_right);

        return left > right ? left + 1 : right + 1;
    }

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

private:
    Node* _root = nullptr;
};

